package com.leetcode.根据算法进行分类.滑动窗口相关;

/**
 * @author: xiaomi
 * @date: 2021/2/6
 * @description: 1423. 可获得的最大点数
 * https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/
 */
public class B_1423_可获得的最大点数 {

    public static void main(String[] args) {
        B_1423_可获得的最大点数 action = new B_1423_可获得的最大点数();
        test1(action);
        test2(action);
        test3(action);

    }

    public static void test1(B_1423_可获得的最大点数 action) {
        //55
        int[] cardPoints = new int[]{9, 7, 7, 9, 7, 7, 9};
        int k = 7;
        int res = action.maxScore(cardPoints, k);
        System.out.println("res = " + res);
    }

    public static void test2(B_1423_可获得的最大点数 action) {
        //248
        int[] cardPoints = new int[]{100, 40, 17, 9, 73, 75};
        int k = 3;
        int res = action.maxScore(cardPoints, k);
        System.out.println("res = " + res);
    }

    public static void test3(B_1423_可获得的最大点数 action) {
        //12
        int[] cardPoints = new int[]{1,2,3,4,5,6,1};
        int k = 3;
        int res = action.maxScore(cardPoints, k);
        System.out.println("res = " + res);
    }

    /**
     * 本想用 DP 进行求解，但是发现其后的状态跟之前走的轨迹有关系，不符合 DP 的性质。
     * --
     * 逆向思维：使用滑动窗口计算出 min ,最后考虑用 sum-min 即可
     * @param cardPoints
     * @param k
     * @return
     */
    public int maxScore(int[] cardPoints, int k) {
        int len = cardPoints.length;


        int interval = len - k;
        int sum = 0;

        for (int i = 0; i < interval; i++) {
            sum += cardPoints[i];
        }
        //欲求出最小的差值
        int min = sum;
        int index = 0;
        int partSum=min;
        for (int i = interval; i < len; i++) {
            sum += cardPoints[i];
            partSum = partSum - cardPoints[index++] + cardPoints[i];
            min = Math.min(min, partSum);
        }
        return interval == 0 ? sum : sum - min;
    }
}
